package class2;

/**
 * 给一个无序数组，找出局部最小的值或位置
 * 1.判断边界
 * 2.使用二分查找法
 */
public class Code06_RangeMin {

    public static void main(String[] args) {
        int[] arr = {3, 2, 8, 5, 53, 14, 7, 4, 9, 11, 13};
        int index = findRangeMinNum(arr, 0, arr.length - 1);
        System.out.println(index);
        arr = new int[]{7, 6, 5, 9, 6, 8, 12};
        index = findRangeMinIndex(arr);
        System.out.println(index);
        index = findRangeMinIndex2(arr);
        System.out.println(index);
    }


    public static int findRangeMinIndex(int[] arr) {
        // 当数组为 null 时，返回 -1
        if (arr == null || arr.length == 0) return -1;
        // 当 length==1 或者 arr[0]<arr[1]时，返回 0
        if (arr.length == 1 || arr[0] < arr[1]) return 0;
        // 倒数第二个数 > 倒数第一个数时，
        if (arr[arr.length - 2] > arr[arr.length - 1]) return arr.length - 1;

        int L = 0;
        int R = arr.length - 1;
        int ans = -1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid - 1] > arr[mid] && arr[mid + 1] > arr[mid]) { // 时局部最小值
                ans = mid;
                return ans;
            } else {
                // 10 3 5 9 6 7 12
                if (arr[mid] > arr[mid - 1]) { // 中间元素比左邻元素大，因此局部最小值可能在左半部分，更新 right = mid - 1。
                    R = mid - 1;
                } else if (arr[mid] > arr[mid + 1]) { // 中间元素比右邻元素大，因此局部最小值可能在右半部分，更新 left = mid + 1
                    L = mid + 1;
                }
            }
        }
        return ans;

    }

    // 返回局部最小值的下标
    public static int findRangeMinIndex2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1; // no exist
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    // 返回最小的值
    public static int findRangeMinNum(int[] arr, int L, int R) {
        if (arr == null && arr.length == 0) return 0;

        if (arr.length == 2) {
            return Math.min(arr[0], arr[1]);
        }

        if (L == R) return arr[L];

        int mid = L + ((R - L) >> 1);
        int l = findRangeMinNum(arr, L, mid);
        int r = findRangeMinNum(arr, mid + 1, R);
        return Math.min(l, r);
    }
}

